﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

class Sol209
{
    public int MinSubArrayLen2(int[] arr,int target)
    {
        int resEnd=arr.Length;
        int resStart = -1;
        int end = 0;
        for (int start = 0; start < arr.Length; start++)
        {
            
            int sum = arr[end];

            while (sum < target)
            {
                end++;//这个方法会导致，如果没有合适的区间，end就会一直增加，下面这个函数会越界
                if(end< arr.Length)
                {
                    sum += arr[end];
                }
                else
                {
                    break;
                }
              
            }
            if (end - start < (resEnd - resStart))
            {
                resStart = start;
                resEnd=end;//更新返回的区间
            }

        }



        return 0;
    } public int MinSubArrayLen3( int target,int[] nums)//滑动窗口法
    {
        int resEnd=nums.Length;
        int resStart = -1;
        int start = 0;
        int sum = 0;
        for (int end = 0; end < nums.Length; end++)
        {
            
           sum += nums[end];

            while (sum >target)//这个方法只可以处理刚好相等的，而且时间复杂度还是n2
            {
                sum -= nums[start];
                start++;
                
            }
            if (sum == target)
            {
                if (end - start < (resEnd - resStart))
                {
                    resStart = start;
                    resEnd = end;//更新返回的区间
                }

            }

        }

        if(resStart == -1)
        {
            return 0;
        }
        else
        {
            return resEnd - resStart+1;
        }

       
    }public int MinSubArrayLen( int target,int[] nums)//滑动窗口法
    {
        int len=nums.Length;
        int resEnd=nums.Length;
        int resStart = -1;
        int start = 0;
        int sum = 0;
        int end = 0;
       
          while(end<len)
        {
            sum += nums[end];

            while (sum >= target)
            {

                if (end - start < (resEnd - resStart))
                {
                    resStart = start;
                    resEnd = end;//更新返回的区间
                }

                sum -= nums[start];
                start++;

            }
         

            end++;

        }



        if (resStart == -1)
        {
            return 0;
        }
        else
        {
            return resEnd - resStart+1;
        }

       
    }
    
    
    
    
    public int MinSubArrayLen0( int target,int[] nums)//暴力，两次循环
    {
        int resEnd=nums.Length;
        int resStart = -1;
       
        

        for (int start = 0; start < nums.Length; start++)
        {
            int sum = 0;//找一下以start开头的符合要求的
            for (int end = start; end < nums.Length; end++)
            {

                sum += nums[end];


                if (sum >= target)
                {
                    if (end - start < (resEnd - resStart))
                    {
                        resStart = start;
                        resEnd = end;//更新返回的区间
                    }
                    break;//提前结束，不然越来越大
                }

            }

           

        }
        if (resStart == -1)
        {
            return 0;
        }
        else
        {
            return resEnd - resStart + 1;
        }
    }

}


class Program209
{
    static void Main209(string[] args)
    {



        int[] nums = { 2, 3, 1, 2, 4, 3 };
        int target = 7;
        //target = 4;
        //nums = [1, 4, 4];
        Sol209 s = new Sol209();
       int res=s.MinSubArrayLen( target,nums);
        Console.WriteLine(res);
        Console.ReadKey();


    }
}
